In Virtual Private Local Area Network (LAN) Service (VPLS) multi-homing environments, there may be instances when a customer site is multi-homed to more than one provider edge device (PE) in order to provide redundant connectivity. Each PE creates a pseudo-wire (PW), which constitutes the data plane, to connect to every other PE, so that a fully-meshed connection scheme is established. Regardless of the number of customer sites serviced by the PE, only one pseudo-wire (PW) is created on the PE with respect to another PE. For example, a PE that services two customer sites may establish only one PW that provides a connection from the PE to another PE. Under this framework, when a communication link between one of the customer sites and the PE fails, the PE tears down its PW, and then rebuilds its PW. Unfortunately, during this procedure, traffic to and from the other customer site to which the PE services is adversely impacted.